package io.github.consoles.dsa;

import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * Created by yiihua-013 on 17/2/6.
 * <p>
 * 数组实现自动扩容的队列
 *
 * 优化每次出队列重排数组带来的严重的性能问题
 */
public class ArrayQueue2<Item> implements Iterable<Item> {

    private Item[] arr;
    private int    count;
    private int    first;
    private int    last;

    private static final int DEFAULT_CAPACITY = 1;

    public ArrayQueue2() {
        this(DEFAULT_CAPACITY);
    }

    public ArrayQueue2(int cap) {
        arr = (Item[]) new Object[cap];
        count = cap;
    }

    public boolean isEmpty() {
        return first == last;
    }

    public int size() {
        return last - first;
    }

    public void enqueue(Item item) {
        if (last == count) resize(2 * size());
        arr[last++] = item;
    }

    public Item dequeue() {
        if (isEmpty()) throw new RuntimeException("Queue is Empty");
        if (size() < count / 4) resize(2 * size());
        return arr[first++];
    }

    /**
     * 队列扩容
     */
    private void resize(int cap) {
        Item[] tmp = (Item[]) new Object[cap];
        int j = 0;
        for (int i = first;i < last;i++){
            tmp[j++] = arr[i];
        }
        arr = tmp;
        count = cap;
        last -= first;
        first = 0;
    }

    private class ArrayQueueIterator implements Iterator<Item> {

        private int index = first;

        @Override
        public boolean hasNext() {
            return index < last;
        }

        @Override
        public Item next() {
            if (!hasNext()) throw new NoSuchElementException();
            return arr[index++];
        }
    }

    @Override
    public Iterator<Item> iterator() {
        return new ArrayQueueIterator();
    }
}
